The invention relates to data error detection and correction.
Error correction codes (ECCs) have been developed that both detect and correct certain errors. One well known class of ECC algorithm is the "Hamming codes," which are widely used for error detection and correction in digital communications data storage systems. The Hamming codes are capable of detecting multiple bit errors and correcting single bit errors. A detailed description of the Hamming codes is found in Shu Lin et al., "Error Control Coding, Fundamentals and Applications," Chapter 3 (1982). Another well known ECC algorithm is the "Reed-Solomon code" widely used for error correction in the compact disk industry. A detailed description of this ECC algorithm is found in Hove et al., "Error Correction and Concealment in the Compact Disk System," Philips Technical Review, Vol. 40, No. 6, pp. 166-172 (1980). The Reed-Solomon code is able to correct two errors per word. Other conventional ECC algorithms include the b-adjacent error correction code described in D. C. Bossen, "B-Adjacent Error Correction," IBM J. Res. Develop., pp. 402-408 (July 1970), and the odd weight column codes described in M. Y. Hsiao, "A Class of Optimal Minimal Odd Weight Column SEC-DED Codes," IBM J. Res. Develop., pp. 395-400 (July 1970). The Hsiao codes, like the Hamming codes, are capable of detecting double bit errors and correcting single bit errors. The Hsiao codes use the same number of check bits as the Hamming codes (e.g., 8 check bits for 64 bits of data), but are superior in that hardware implementation is simplified and speed of error detection is improved.
Another type of ECC algorithm has been used in computer memory sub-systems, which is described in copending and commonly assigned U.S. patent application Ser. No. 07/955,923, filed Oct. 2, 1992, entitled "Error Correction System for N Bits Using Error Correction Designed for Fewer than N Bits." The ECC algorithm described in this prior application, when coupled with a particular data distribution architecture, obtains the advantages of the Hamming codes with the same overhead (8 check bits for 64 bits of data), but also is able to correct any single 4-bit wide error.